package InterviewTest.q0406_inorderSuccessor;

import CommonClass.Common.TreeNode;

public class Solution_2 {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;
        /*
        这里的if判断代表直接使用p节点来找它的后继节点
        也就是按照左 根 右的顺序 找p的右子树中的左叶子节点
        可以去除这个判断 直接使用下面的while求解
         */
        if (p.right != null) {
            successor = p.right;
            while (successor.left != null) {
                successor = successor.left;
            }
            return successor;
        }

        /*
        结合二叉搜索树的性质来找后继节点
         */
        TreeNode node = root;
        while (node != null) {
            if (node.val > p.val) {
                // 如果是大于 则需要去左侧找 并且记录当前节点
                successor = node;
                node = node.left;
            } else {
                // 小于则不需要记录 直接去右侧找
                node = node.right;
            }
        }
        return successor;
    }

}
